ARC 037 B - バウムテスト

UnionFind+閉路検出

辺を順に見ていき、すでに同じグループに属している辺同士をuniteしようとした場合を閉路とする。

Union時に処理を行える汎用化UnionFindのライブラリを作成した

code: arc037_b.js

solve() {

const nm = input.nextIntArr();

const uvs = input.nextIntRange(nm1).map(l => l.map(e=>e-1));

const loop = new Unit('loop');

loop.init = () => false;

loop.union = (x,y,rmin,rmax) => {

loop.datarmin =

(loop.datarmin || loop.datarmax || rmin == rmax);

}

const uf = new UnionFind(nm0,loop);

for (const uv of uvs) { const root = uf.unite(uv0,uv1); }

return uf.getData('ref').filter((e,i) => e == i && !uf.get('loop',i)).length;

}